#include<bits/stdc++.h>
using namespace std;


void Heapfi(vector<int>& nums,int n,int i){
    while(1){
        int maxPos=i;
        if(i*2<=n && nums[i]<nums[2*i]){
            maxPos=2*i;
        }
        if(i*2+1<=n && nums[maxPos]<nums[2*i+1]){
            maxPos=2*i+1;
        }
        if(maxPos==i){
            break;
        }
        swap(nums[i],nums[maxPos]);
        i=maxPos;
    }
}


void HeapSort(vector<int>& nums, int n){
    for(int i=n/2;i>=1;--i){
        Heapfi(nums,n,i);
    }
    int k=n;
    while(k>0){
        // cout<<nums[1]<<" ";
        swap(nums[1],nums[k]);
        --k;
        Heapfi(nums,k,1);
    }
}



int main(int argc, char const *argv[])
{
    vector<int> nums={0,7,6,5,4,3,2,1};
    HeapSort(nums,7);
    for(int i=0;i<8;++i){
        cout<<nums[i]<<" ";
    }
    cout<<endl;
    return 0;
}
